There are many imaging and communications systems which employ an image which is not uniformly sampled, and from which a full image is reconstructed. The human visual system provides an example from nature wherein the spatial positions of the rods and cones provide random samples of the scene imaged on the retina, from which a full image is subsequently reconstructed. Another example of a system dealing with two dimensional signals or images is found in video and electronic still applications where charge coupled device (CCD) sensors are often used. CCDs may have defects or non-valid pixels, and thereby have incomplete information at some pixel locations. Additionally, in the case where a single sensor is used to capture multiple two-dimensional channels, for example the color channels of an image, then a color filter array (CFA) is often employed to discriminate between the color channels. The CFA acts as either a regular or random sampling device in each of the color channels and may, in addition have defects which results in additional incomplete information.
There are many situations in which random sampling of a signal has significant advantages over regular sampling, an excellent review of such advantages being provided by U.S. Pat. No. 4,574,311 entitled "Random Array Sensing Devices." Highlighted in the above-mentioned application is the fact that aliasing can occur when a non-bandlimited signal is sampled. Aliasing is particularly noticeable (as low frequency periodic information) when a non-bandlimited high frequency periodic signal is sampled on a regular sampling grid. Aliasing may also occur when a non-bandlimited high frequency signal is randomly sampled, but in this case the artifact is manifest as broad band noise which is less objectionable.
Various approaches to solving the reconstruction problem have been presented. The above-mentioned U.S. Pat. No. 4,574,311 discloses a triangulation based linear interpolation method that utilizes the spatial distance between irregular samples to reconstruct a continuous image: This requires the calculation of multiple distances at each pixel location and limits the contribution to the reconstruction to the nearest neighbour samples.
In many reconstruction schemes, iterative methods are used, such as the Adaptive Weights Method, an iterative Fourier interpolation technique, described in Benedetto and Frazier, Wavelets: Mathematics and Applications, CRC Press, 1994, pp 336-359. A comprehensive review of approaches to reconstructing irregularly sampled images can be found in IEEE Transactions on Image Processing, Vol. 6, No. 4, April 1997, `Computationally Attractive Reconstruction of Bandlimited Images from Irregular Samples` by Strohmer. Again, recursive or iterative methods are discussed and it is noted that in many cases it is difficult or impossible to extend the methods applicable to one-dimensional signals for use in the reconstruction of signals of two or more dimensions, such as images.